//题目:
// 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

// 示例 1:
// 输入: nums = [1,1,1,2,2,3], k = 2
// 输出: [1,2]

// 示例 2:
// 输入: nums = [1], k = 1
// 输出: [1]

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>

using namespace std;

//代码:
class Solution 
{
    struct compare
    {
        bool operator()(const pair<int,int>& pir1,const pair<int,int>& pir2)
        {
            return pir1.second>pir2.second;
        }
    };
public:
    void quicksort(vector<pair<int,int>>& v_pir,int left,int right,int pos,vector<int>& ret)
    {
        if(left>=right) 
        {
            if(left==right && left<=pos)
                ret.push_back(v_pir[left].first);
            return;
        }

        int std_val=v_pir[(left+right)/2].second;
        //三指针法区域划分
        int i=left-1,cur=left,j=right+1;
        while(cur<j)
        {
            if(v_pir[cur].second>std_val) swap(v_pir[++i],v_pir[cur++]);
            else if(v_pir[cur].second==std_val) cur++;
            else swap(v_pir[--j],v_pir[cur]);
        }
        //获取指定元素
        for(int k=i+1;k<=min(pos,j-1);k++)
            ret.push_back(v_pir[k].first);

        quicksort(v_pir,left,i,pos,ret);
        if(pos>=j) quicksort(v_pir,j,right,pos,ret);
    }
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;//<val,count>
        for(auto x:nums)  hash[x]++;
        //法一：根据pir.second建小堆，容量为k ———— n(logk)
        // priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
        // for(const auto& pir:hash)
        // {
        //     if(pq.size()<k) pq.push(pir);
        //     else if(pir.second>pq.top().second) pq.pop(),pq.push(pir);
        // }
        // //得到结果
        // vector<int> ret;
        // while(!pq.empty()) ret.push_back(pq.top().first),pq.pop();
        // return ret;
        vector<pair<int,int>> v_pir;
        for(const auto& pir:hash) v_pir.push_back(pir);
        vector<int> ret;
        //法二：快排思想
        quicksort(v_pir,0,v_pir.size()-1,k-1,ret);

        return ret;
    }
};